package LeetCode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}21:33
 */
public class LeetCode983 {//最低票价问题
    int[] costs;
    Integer[] memo;
    Set<Integer> dayset;
    public int mincostTickets(int[] days, int[] costs) {
        this.costs = costs;
        memo = new Integer[366];
        dayset = new HashSet<>();
        for (int day : days) {
           dayset.add(day);
        }
        return dp(1);
    }

    public int dp(int i){
        if (i > 365){
            return 0;
        }
        if (memo[i] != null){
            return memo[i];
        }

        if (dayset.contains(i)){//必须旅行的时间
            memo[i] = Math.min(Math.min(dp(i+1)+costs[0],dp(i+7)+costs[1]),dp(i+30)+costs[2]);//注意这里用的递归是为了实现从后往前来进行计算
        }else {//不必要旅行时间
            memo[i] = dp(i+1);
        }
        return memo[i];//最后返回的i=1那天的钱，因为是从后往前来的
    }
    /*
    * 复杂度分析

时间复杂度：O(W)O(W)，其中 W = 365W=365 是旅行计划中日期的最大值，我们需要计算 WW 个解，而每个解最多需要查询 33 个其他的解，因此计算量为 O(3 * W)=O(W)O(3∗W)=O(W)。

空间复杂度：O(W)O(W)，我们需要长度为 O(W)O(W) 的数组来存储所有的解。
    * */






    /*
    * 时间复杂度：O(N)O(N)，其中 NN 是出行日期的数量，我们需要计算 NN 个解，而计算每个解的过程中最多将指针挪动 3030 步，计算量为 O(30 * N)=O(N)O(30∗N)=O(N)。

空间复杂度：O(N)O(N)，我们需要长度为 O(N)O(N) 的数组来存储所有的解。

    * */
    class Solution {
        int[] days, costs;
        Integer[] memo;
        int[] durations = new int[]{1, 7, 30};

        public int mincostTickets(int[] days, int[] costs) {
            this.days = days;
            this.costs = costs;
            memo = new Integer[days.length];
            return dp(0);
        }

        public int dp(int i) {
            if (i >= days.length) {
                return 0;
            }
            if (memo[i] != null) {
                return memo[i];
            }
            memo[i] = Integer.MAX_VALUE;
            int j = i;
            for (int k = 0; k < 3; ++k) {
                while (j < days.length && days[j] < days[i] + durations[k]) {
                    j++;
                }
                memo[i] = Math.min(memo[i], dp(j) + costs[k]);
            }
            return memo[i];
        }
    }






}
